/**
 * @brief 这是卡特兰数在二叉树里面的一个体现
 * 题目连接:https://leetcode-cn.com/problems/unique-binary-search-trees
 * @param n
 * @return int
 */

#include <vector>
using namespace std;
int numTree(int n) {
  vector<int> ans(n + 1, 0);
  ans.at(0) = ans.at(1) = 1;

  for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      ans.at(i) += (ans.at(j - 1) * ans.at(i - j));
    }
  }
  /**
   * @brief 也可以转换为下面的
   * for(int j=0;j<i;++i){
   *    ans.at(i)+=(ans.at(j)*ans.at(i-j-1));
   * }
   *
   */

  return ans.at(n);
}
